package 力扣日常刷题.木23一月.第03天303;

import java.util.HashMap;

/**
 * @author 帅小伙
 * @date 2022/3/3
 * @description
 */
public class Demo23和为k的倍数的最短子数组 {

    //前缀和
    public int subarraysDivByK(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];

        for (int i = 0; i < n; i++) {
            sum[i+1] = sum[i] + nums[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i; j++) {
                if((sum[j+i+1] - sum[j])%k == 0) ans++;
            }
        }
        return ans;
    }


    //哈希表+逐一统计
    // 同余两个相减就是  次数
    public int subarraysDivByK2(int[] nums, int k) {
        int sum = 0,ans = 0;
        int[] mods = new int[k];
        mods[0] = 1;
        for (int num : nums) {
            sum += num;
            // 避免负数
            int mod = (sum % k + k)%k;
            ans += mods[mod];
            ++mods[mod];
        }
        return ans;
    }


}
